Garbage Collection

Abstract

在堆中分配且通过任何程序变量形成的指针链都无法到达的记录被称为垃圾 garbage。垃圾占据的存储空间应当被回收，以便分配给新的记录，这一过程叫做垃圾收集 Garbage Collection。

标记 - 清扫式收集

算法流程

所有的程序变量都构成了图中的根
（标记阶段）通过 深度优先搜索算法 从根开始标记变量
- 如果变量 x 为指针，则标记 x 指向的内存，并遍历内存的存储内容
- 如果变量 x 不是指针，结束遍历
（清扫阶段）从堆中的第一个地址出发
- 如果该地址已被标记，则去除标记
- 如果该地址未被标记，则将其加入空闲表

「引用计数」优化

引用计数 reference count
标记 - 清扫式收集的初始算法复杂度较高，可以使用引用计数进行优化
算法流程：由编译器实现引用计数
- 每当将 p 存储到 $x . f_{i}$ 时
  - 增加 p 的引用计数
  - 减少 $x . f_{i}$ 以前指向的记录的引用计数
- 每当某个记录 r 的引用计数减少为 0
  - 将 r 放到空闲表中
  - 减少 r 指向的所有其他记录的引用计数

复制式收集

复制式收集 copying garbage collection
复制式收集没有碎片问题
堆中的旧区域被称作 from-space，新区域称作 to-space

收集初始化

将初始化指针 next 指向 to-space
当在 from-space 发现一个可达记录
- 将它复制到 to-space 的 next 所指的位置
- 使 next 增加该记录的大小

转递 forwarding

使指向 from-space 的指针指向 to-space
- 如果指针 p 指向 from-space 中一个还未复制的记录
  - 将它复制到 next 所指的位置，同时将传递指针赋给 $p . f_{1}$
- 如果指针 p 指向的是 from-space 中的一个已复制过的记录
  - 则满足 $p . f_{1}$ 是一个指明副本在何处的特殊的转递指针（forwarding pointer）
- 如果 p 不是指针，或指向的是 from-space 之外的指针
  - do nothing

Cheney 算法

使用 宽度优先搜索 对可到达数据进行遍历。

scan <-  next <- to-space 的开始
for 每一个根 r
	r <- Forward(r)
while scan < next
	for scan 处的那个记录的每一个域 fi
		scan.fi <- Forward(scan.fi)
	scan <- scan + scan 处的那个记录的大小

Pasted image 20230525112145.png